#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @Author  : 邢建辉
# @Email   : xjh_0125@sina.com
# @Time    : 2021/12/27 16:27
# @Software: PyCharm
# @File    : l1334_find_the_city.py


class Solution(object):
    def findTheCity(self, n, edges, distanceThreshold):
        """
        :type n: int
        :type edges: List[List[int]]
        :type distanceThreshold: int
        :rtype: int
        """
        dp = [[float('inf') for i in range(n)] for i in range(n)]
        for tp in edges:
            dp[tp[0]][tp[1]] = tp[2]
            dp[tp[1]][tp[0]] = tp[2]
        for i in range(n):
            dp[i][i] = 0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
        res, min_c = float('-inf'), n
        for tp in enumerate(dp):
            tmp_c = 0
            idx, arr = tp
            for j in arr:
                tmp_c += 1 if j <= distanceThreshold else 0
            if tmp_c <= min_c:
                min_c = tmp_c
                res = max(res, idx)

        return res


if __name__ == '__main__':
    s = Solution()
    n, edges, distanceThreshold = 4, [[0, 1, 3], [1, 2, 1], [1, 3, 4], [2, 3, 1]], 4
    res = s.findTheCity(n, edges, distanceThreshold)
    print(res)
